Large networks, such as the Internet, provide the infrastructure for many peer-to-peer systems and are now being used to provide a variety of services to users. Some recent Internet applications require high bandwidth. Live, high-quality, streaming video, video conferencing, and graphic-intensive multiplayer games are examples of high-bandwidth applications.
A fundamental challenge in effectively utilizing high-bandwidth network services is to provide these services and other data transmission without affecting the quality of the services. Routing is a major factor in providing these services. Use of overlay networks and overlay routing to provide these services instead of using the default Internet Protocol (IP) routing has been receiving great interest. It has been shown that overlay routes can give better performance over native IP routes. However, selecting particular overlay routes for actual use that provide better performance than a default IP route is difficult. Metrics, such as latency or loss rate, have been suggested for use in selecting new routes. However, these metrics vary considerably over time, and as a result, a new route selected based on past measurements can provide worse performance than the default IP path by the time the selected new path is implemented.